﻿using System;
using System.Collections;
using System.Collections.Generic;
using UnityEngine;

/// <summary>
/// 并查集
/// </summary>
public class UnionSet {

	Dictionary<object,object> data = new Dictionary<object,object>();

	/// <summary>
	/// 判断是否所有元素都在一个集合中
	/// </summary>
	public bool IsOneSet {
		get {
			if(data.Count==0) return true;
			var firstE = data.GetEnumerator();
			firstE.MoveNext();
			object firstI = firstE.Current.Key;
			foreach(var i in data) {
				if(Find(i.Key)!=Find(firstI))
					return false;
			}
			return true;
		}
	}

	/// <summary>
	/// 获取某个元素对应的根结点
	/// </summary>
	/// <param name="index">索引</param>
	/// <returns>根结点的索引</returns>
	public object Find(object index) {
		if(!data.ContainsKey(index)) data.Add(index,index);
		object i = index, r = index, j;
		while(data[r]!=r) r=data[r];
		while(i!=r) {
			//压缩路径
			j=data[i];
			data[i]=r;
			i=j;
		}
		return r;
	}

	/// <summary>
	/// 合并两个元素
	/// </summary>
	/// <param name="a"></param>
	/// <param name="b"></param>
	public void Union(object a,object b) {
		a=Find(a);
		b=Find(b);
		data[b]=a;
	}

	/// <summary>
	/// 获取某个元素对应的根结点
	/// </summary>
	/// <param name="index">索引</param>
	/// <returns>根结点的索引</returns>
	public object this[int index] { get { return this.Find(index); } }

}